
\subsection{Optimal polygon triangulation}
\label{sec:polygonTriangulation}

\subsubsection{Relevance for the project}The LMT skeleton may contain holes. These hole polygons are simple polygons with a high probability and therefore can be triangulated optimally in polynomial time ($O(n^3)$) using a dynamic programming approach.
\begin{figure}[h]
\includegraphics[width=60mm]{lmt_hole.png}
\caption{A LMT skeleton that contains a hole polygon}
\end{figure}

\subsubsection{Finding the holes in the LMT skeleton}

The first step is to find the hole polygons inside the LMT skeleton. This is achieved by exploiting the remaining candidate edges to get sets of vertices for each hole polygon. The connected components of the graph induced by the remaining candidate edges and their intersections are disjoint sets of edges. Each one of these sets contains all of the vertices of the corresponding polygonal hole as the end vertices of its edges. In other words, all vertices of a polygonal hole are incident to edges of exactly one connection component of the aforementioned induced graph.

To clarify the observation let $H$ be a connected component and assume there is a vertex $b$ on the corresponding hole polygon $p$ that is not incident to any edge in $H$. Let $a$ and $c$ be the neighbors of $b$ on the boundary of $p$. The corner $\overline{abc}$ may be either concave or convex. A concave corner implies that contrary to the assumption, there has to be an edge incident to $b$; otherwise no valid triangulation would be possible. In the convex case, consider the line segment $\overline{ac}$. If $b$ is not an endpoint of any of the edges of the connected component, and no other vertex of $p$ is within the triangle $\Delta(a,b,c)$, there cannot be a candidate edge intersecting $\overline{ac}$. Thus $\overline{ac}$ would have been removed from candidateEdges and added to edgesIn by the LMT algorithm and $b$ could not be on the perimeter of $p$, a contradiction of the assumption.

If there are vertices of $p$ within $\Delta(a,b,c)$, let $d$ be the closest vertex to $b$. The edge $ad$ cannot be intersected by any other edge of the connected component, therefore it must have been added to edgesIn by the LMT algorithm. Contrary to the assumption, either $a$ or $c$ would not be a neighbor of $b$.


\paragraph{}Once a set of vertices for every hole polygon is found, a valid polygon may be constructed. Identifying the vertices of a polygon does not suffice since the order of the vertices matters. Figure 1 illustrates the possibility of multiple cycles within a polygon: Vertex $1$ and vertex $2$ are both part of the polygon, but the edge between them is not. The algorithm must find the cycle containing all vertices of the polygon. This is achieved using a slightly modified depth-first search (cycle search).

\subsubsection{Optimal polygon triangulation algorithm}Given a convex polygon $P = \{v_1, ..., v_n\}$ in anti-clockwise order and a weight function $w$ that assigns a weight to each triangle (for example the sum of all edge lengths), we define $t[i,j]$ as the weight of the optimal triangulation of the polygon right to the directed chord between $v_i$ and $v_j$. The weight between two neighbored vertices is $0$. Otherwise, $v_i$ and $v_j$ form a triangle together with a third vertex k with $i<k<j$. $t[i,j]$ is the weight of this triangle plus the minimal triangulation cost of the polygon right to the chord between $i$ and $k$ ($t[i,k]$) and the minimal triangulation cost of the polygon right to the chord between $k$ and $j$ ($t[k,j]$):\\\\
$t[i,j] = \begin{cases}
0 & \text{if }j = i+1\\
min_{i<k<j}(t[i,k] + t[k,j] + w(v_i,v_k,v_j)) & \text{if } j > i + 1
\end{cases}$\\\\
The weight of $t[0, n]$ is the summed weight of all triangles that are part of the optimal triangulation of the complete polygon. This means that this method is not acceptable for triangulation metrics like Delaunay triangulation because the algorithm always minimizes the sum of all triangles.\\
The different weight functions are defined in the classes implementing the interface MinimalityMetric. \\\\
The algorithm only works with convex polygons, but often the LMT holes are not convex. In order to work with all simple polygons correctly, the algorithm must check for each chord between $i$ and $j$ if it is completely inside the polygon. If it is not, we define $t[i,j]$ as $\infty$, because the chord is not part of a valid triangulation and must not be chosen.\\\\
$t[i,j] = \begin{cases}
0 & \text{if }j = i+1\\
\infty & \parbox{4cm}{\flushleft{if the chord between $i$ and $j$ is not inside the polygon}}\\
min_{i<k<j}(t[i,k] + t[k,j] + w(v_i,v_k,v_j)) & \text{if } j > i + 1
\end{cases}$\\\\
